package leetcode.leetcode25xx.leetcode2554;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

class SolutionTest {

    @Test
    void test1() {
        // banned = [1,6,5], n = 5, maxSum = 6
        //Output: 2
        //Explanation: The banned numbers are [1,6,5]. The numbers [2,3] are not banned and 2 + 3 = 5 <= 6.
        assertEquals(2, new Solution().maxCount(new int[]{1, 6, 5}, 5, 6));
        assertEquals(2, new Solution2().maxCount(new int[]{1, 6, 5}, 5, 6));
    }

    @Test
    void test2() {
        //banned = [11], n = 7, maxSum = 50
        //Output: 7
        //Explanation: The banned numbers are [11]. The numbers [1,2,3,4,5,6,7] are not banned and 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 <= 50.
        assertEquals(7, new Solution2().maxCount(new int[]{11}, 7, 50));
    }

    @Test
    void test3() {
        int[] banned = {2761, 987, 3493, 6445, 6308, 4384, 5579, 3758, 6233, 5998, 3586, 5775, 2280, 6748, 1661, 4503, 4225, 6097, 6396, 4857, 3219, 2914, 3988, 2587, 2478, 1649, 2653, 2774, 3867, 6175, 5645, 3711, 3810, 1520, 5646, 5503, 3371, 6665, 5106, 1830, 77, 3398, 1651, 5718, 3103, 4798, 3484, 2446, 644, 2082, 4217, 524, 282, 4464, 1102, 6248, 5356, 4989, 4452, 1913, 6201, 558, 373, 2892, 79, 2518, 736, 3432, 3592, 2711, 1956, 3752, 5253, 1268, 1659, 3045, 4340, 3564, 5838, 1394, 2107, 6728, 4487, 1806, 4346, 4753, 4940, 4823, 6434, 1883, 255, 5765, 4903, 1230, 5984, 1630, 3042, 2620, 6932, 133, 3155, 6946, 5254, 2882, 6200, 2071, 6972, 3659, 4801, 5934, 6904, 4202, 1049, 6971, 5552, 1057, 4470, 3639, 170, 6405, 5114, 909, 3623, 4711, 2267, 3718, 199, 5362, 1559, 5201, 5810, 3904, 5983, 3142, 354, 1985, 561, 2205, 5666, 4778, 6986, 613, 6004, 1005, 2870, 4261, 123, 5044, 2625, 3000, 939, 1948, 180, 492, 2164, 5690, 1560, 4915, 4180, 5516, 1615, 811, 4336, 532, 5478, 3176, 3573, 5606, 1881, 2561, 1787, 6802, 1364, 3525, 3274, 1400, 3033, 2572, 6205, 6045, 1226, 3106, 3947, 6947, 2281, 4421, 812, 5790, 5593, 6920, 254, 5101, 6355, 2573, 4129, 937, 2332, 6860, 4931, 6832, 4285, 6664, 6172, 2673, 3760, 6503, 6774, 4492, 6970, 3833, 6293, 4719, 3289, 5015, 2390, 3375, 2932, 5071, 648, 3498, 961, 1802, 4355, 14, 3282, 1265, 2148, 3241, 4948, 2311, 1529, 1419, 3674, 5849, 5572, 4578, 5445, 6851, 6491, 2245, 1471, 1374, 3570, 1504, 355, 5766, 5285, 6059, 2961, 3243, 365, 2451, 3684, 1873, 3709, 3215, 3324, 309, 3456, 5331, 1823, 3765, 619, 5834, 6924, 888, 2476, 2365, 4637, 2665, 5498, 5090, 986, 5444, 4672, 1020, 5836, 732, 5559, 5174, 6429, 3597, 3955, 10, 6671, 4527, 1827, 2069, 2379, 6221, 5324, 3287, 5208, 5223, 5431, 1920, 4248, 2534, 2889, 193, 783, 5677, 1130, 495, 6383, 1794, 760, 3703, 6875, 1002, 5643, 3478, 2862, 319, 5414, 5288, 562, 4850, 2060, 4053, 3084, 3682, 6304, 2021, 2807, 1416, 5692, 3645, 2121, 228, 5631, 4932, 4076, 2187, 5763, 1597, 5337, 5581, 1237, 3297, 1089, 1229, 5630, 2965, 3347, 1849, 2649, 6867, 4939, 4807, 280, 5112, 2290, 6969, 3192, 6793, 425, 5573, 5653, 4606, 1474, 3352, 5550, 3650, 3675, 1090, 1023, 5571, 1362, 6131, 1740, 4951, 3730, 332, 2868, 5225, 6287, 5541, 3406, 5065, 5870, 2246, 1387, 2502, 5633, 3528, 5256, 5700, 5089, 6741, 3120, 6849, 3681, 3445, 2301, 5603, 2685, 4843, 3686, 1302, 1370, 4660, 3227, 1641, 5075, 1393, 2627, 6313, 6752, 6197, 1475, 2664, 5086, 971, 4368, 2563, 5155, 5967, 5393, 4863, 4718, 3036, 2590, 718, 407, 69, 1245, 4706, 2794, 4428, 1563, 6984, 1126, 573, 3970, 6850, 4271, 3216, 2793, 6328, 1462, 196, 1572, 4613, 4095, 5762, 5185, 6750, 3507, 1884, 3572, 2180, 325, 1377, 6980, 3927, 3225, 2756, 1286, 3301, 779, 340, 2910, 3497, 2656, 5869, 747, 1199, 5138, 6079, 1408, 4943, 6699, 2597, 4911, 404, 5932, 23, 1051, 6404, 419, 2091, 770, 6182, 6621, 1523, 6991, 6941, 6181, 588, 4121, 6215, 6015, 5770, 4864, 3228, 5908, 3492, 3739, 5534, 1855, 4828, 204, 3132, 4755, 6813, 2574, 189, 6777, 1500, 2525, 6701, 1892, 4484, 6444, 3488, 5067, 1705, 5028, 4043, 1803, 4853, 6541, 1000, 1491, 6843, 6770, 1113, 4092, 3939, 5127, 3055, 4139, 1115, 4442, 6854, 2968, 2773, 6117, 1857, 3828, 5467, 5019, 1401, 442, 7007, 1293, 5589, 992, 5104, 4290, 3962, 5188, 3906, 3198, 2621, 3385, 3787, 3328, 1494, 2019, 286, 4265, 5136, 839, 6534, 3992, 6388, 2258, 2838, 1108, 5094, 4200, 5001, 7003, 6326, 460, 6961, 6088, 520, 4425, 3751, 1524, 5053, 6237, 6290, 3085, 4528, 6414, 4533, 2839, 117, 8, 1901, 1894, 2815, 4432, 1501, 1997, 2491, 1758, 5147, 2893, 304, 3620, 303, 1412, 5649, 5968, 1796, 1443, 550, 4702, 6900, 5647, 3627, 3998, 2432, 2943, 5748, 731, 3232, 4617, 611, 6823, 312, 567, 1760, 421, 6787, 104, 913, 3316, 4183, 3646, 2343, 2081, 2099, 910, 1448, 5854, 3116, 6500, 1418, 3741, 3550, 4715, 3168, 4375, 3435, 1842, 3226, 6078, 1686, 4301, 4910, 2971, 5448, 990, 764, 6974, 4926, 2677, 4603, 6386, 6274, 744, 6756, 6180, 2172, 3154, 6093, 884, 6960, 2274, 3740, 4050, 4705, 1972, 4348, 5057, 4146, 4341, 1324, 621, 1383, 1004, 5846, 2852, 4974, 4267, 5207, 2605, 5295, 4163, 6483, 2650, 1358, 1013, 609, 6888, 5404, 2826, 1862, 1841, 828, 4194, 778, 5822, 5344, 2849, 6507, 2366, 5542, 1654, 3117, 4107, 5830, 4396, 978, 1117, 1078, 6395, 2536, 3212, 6374, 530, 3400, 7023, 1702, 3633, 999, 1877, 3974, 6029, 6315, 1601, 1458, 1169, 2035, 5313, 1076, 3736, 5270, 5304, 3671, 6945, 4591, 6112, 600, 1427, 2247, 1981, 22, 6346, 1052, 5688, 6825, 6461, 1433, 1031, 5144, 2352, 5517, 3996, 2864, 475, 2735, 6654, 4471, 3978, 1871, 118, 5547, 1219, 4274, 4538, 3338, 3515, 5614, 6905, 655, 4986, 2372, 1337, 37, 3277, 1402, 2186, 3809, 6708, 3842, 4151, 4908, 2249, 5872, 3850, 6327, 4444, 5715, 2167, 2661, 2909, 4641, 5576, 848, 2412, 5443, 5484, 5095, 3473, 1945, 339, 6552, 3571, 3095, 4149, 5930, 87, 2594, 2540, 5152, 6487, 6962, 1332, 519, 4157, 6275, 5012, 2507, 1260, 5705, 5244, 5530, 5548, 5709, 3887, 1832, 6717, 5944, 3415, 1457, 3469, 4813, 6025, 1722, 2612, 5505, 2096, 4167, 3971, 3800, 5054, 1512, 4385, 1805, 3267, 4770, 5040, 6035, 6863, 5286, 6192, 527, 1274, 454, 4144, 5417, 3417, 6562, 3749, 4411, 409, 925, 989, 5925, 3613, 2113, 6884, 4854, 2876, 6842, 566, 618, 493, 4556, 5750, 517, 1557, 5675, 1074, 6910, 7025, 4482, 2726, 30, 4810, 3518, 1936, 3160, 1041, 6504, 6878, 2544, 5263, 4447, 5464, 4116, 5466, 5305, 5109, 855, 3344, 1564, 2922, 4284, 4970, 3920, 964, 5461, 5405, 3490, 6271, 2714, 3336, 5760, 389, 1724, 6958, 894, 4973, 447, 1311, 2308, 3020, 1817, 4740, 6844, 5747, 4814, 429, 6913, 5377, 1200, 3047, 6735, 2235, 4120, 224, 5298, 5752, 5996, 6525, 472, 6432, 4780, 3683, 132, 1700, 4387, 4028, 5759, 5157, 4168, 5586, 1620, 952, 4559, 120, 5591, 4834, 1521, 3670, 5806, 6456, 4663, 2000, 1220, 6957, 4066, 2031, 4298, 2443, 6353, 3053, 3429, 3637, 4994, 3958, 3882, 4972, 4589, 720, 3391, 2740, 750, 438, 2508, 6224, 2232, 2902, 171, 456, 2722, 4399, 6698, 3509, 2554, 1964, 4950, 1035, 5951, 415, 3389, 4456, 3582, 2221, 6490, 7024, 1021, 4643, 5349, 4356, 1804, 6338, 5355, 3707, 3854, 2124, 11, 4713, 6408, 5964, 2570, 5831, 6277, 806, 856, 423, 3261, 5791, 5648, 129, 1287, 2835, 3377, 3755, 1634, 861, 5955, 2127, 1662, 6441, 1348, 4145, 2846, 4518, 1772, 589, 1644, 2995, 1093, 3539, 6952, 3175, 4328, 6146, 2128, 2847, 4723, 3440, 3327, 5878, 3074, 2358, 5277, 4181, 2757, 1184, 1697, 6066, 308, 6607, 3271, 3240, 4450, 5140, 2373, 4462, 4838, 667, 4958, 842, 1177, 2092, 3296, 2811, 4460, 1106, 2269, 1008, 3770, 2382, 2675, 1060, 4465, 6979, 3299, 5446, 4189, 6141, 5743, 5978, 5713, 3070, 288, 4208, 3088, 1095, 5742, 1731, 2550, 3520, 5736, 6753, 2557, 436, 5582, 4397, 6839, 3706, 381, 1863, 6436, 4563, 6643, 1759, 2991, 984, 4367, 13, 745, 4029, 2879, 1058, 2211, 4766, 111, 2520, 2886, 4087, 143, 1165, 938, 4287, 6702, 1614, 7015, 5829, 5490, 5078, 1908, 4320, 598, 4233, 2340, 2217, 1128, 1123, 2050, 3422, 5575, 19, 5928, 2720, 4684, 1135, 1508, 5153, 4501, 5375, 6218, 781, 3522, 2878, 6646, 4909, 2924, 4830, 4317, 901, 1535, 5064, 2915, 3007, 322, 2582, 135, 5494, 624, 3533, 2841, 6283, 273, 4105, 3954, 3397, 4690, 3785, 4250, 6855, 3652, 2363, 1711, 4177, 1009, 3679, 6452, 2702, 5856, 5320, 4249, 2383, 722, 5175, 446, 2396, 6618, 1976, 1071, 4, 1513, 3607, 4083, 788, 1994, 4236, 3087, 633, 7027, 203, 4445, 186, 3940, 3608, 1795, 785, 6034, 5583, 4622, 1845, 2216, 1962, 2975, 5325, 1086, 6030, 4961, 2654, 2460, 4045, 943, 4935, 6790, 6349, 3035, 6516, 6363, 25, 2484, 4947, 378, 6467, 3372, 1432, 3460, 1577, 5438, 846, 4412, 6602, 4827, 2086, 960, 6622, 6204, 1632, 1965, 2042, 3290, 4272, 682, 3359, 6269, 6827, 5732, 2391, 1665, 1029, 6150, 2966, 5764, 93, 207, 153, 5359, 6786, 4090, 3717, 6531, 209, 1188, 147, 2505, 5919, 5424, 4108, 3259, 6190, 4793, 3933, 4073, 810, 851, 2170, 3814, 6092, 261, 1333, 3418, 6252, 3984, 3546, 5098, 6815, 390, 661, 6838, 5722, 3540, 6373, 2005, 579, 2367, 615, 506, 1310, 2495, 6803, 3008, 3156, 4335, 539, 3321, 5149, 1280, 6091, 942, 2271, 3517, 4435, 3780, 3187, 33, 3599, 4017, 2191, 4170, 1505, 6880, 6241, 3177, 3692, 5217, 3366, 4366, 4565, 2945, 417, 1917, 4968, 3404, 3427, 6225, 1583, 71, 3014, 4543, 4825, 5251, 3544, 6697, 2283, 3830, 2748, 1646, 200, 5246, 560, 5733, 3283, 5022, 6670, 5347, 3050, 6378, 3508, 5781, 6749, 3614, 774, 2989, 5768, 1248, 531, 679, 5061, 3601, 2065, 6714, 4187, 2905, 1438, 6423, 3963, 5945, 1660, 5821, 4654, 3153, 2289, 2417, 3265, 6841, 6521, 5353, 1083, 4745, 6869, 5373, 462, 6381, 6757, 3908, 4598, 557, 6357, 3869, 1514, 1059, 393, 4085, 4506, 6019, 4424, 384, 4400, 3894, 3248, 522, 577, 757, 240, 3668, 3602, 4479, 5257, 5143, 1104, 1160, 6828, 3851, 6206, 4433, 122, 3972, 2331, 4670, 5739, 3643, 3071, 2404, 1839, 1210, 2161, 2724, 4204, 2701, 2821, 3214, 5797, 1321, 6108, 1453, 3242, 6954, 604, 4402, 1631, 2781, 521, 2713, 3044, 1503, 5613, 2206, 658, 6939, 1527, 6891, 2032, 6298, 2599, 2252, 2270, 5215, 1984, 6027, 6453, 2652, 2268, 4773, 5429, 2196, 2628, 3029, 1685, 3885, 368, 6555, 1991, 3877, 1105, 3183, 94, 6370, 709, 5381, 5267, 2926, 819, 906, 433, 6772, 6635, 3653, 1792, 4383, 1950, 3856, 1338, 5196, 5959, 4130, 3364, 6761, 1091, 2303, 4155, 1454, 6729, 1250, 5141, 583, 6576, 1536, 4525, 6028, 4030, 4027, 3881, 4998, 4372, 2316, 1909, 836, 4350, 264, 2453, 5335, 5737, 1355, 2241, 5514, 229, 1365, 6836, 6188, 16, 5264, 5597, 1382, 1158, 4063, 2813, 5909, 956, 1538, 1499, 4109, 2643, 3015, 746, 6580, 3761, 2260, 1055, 4344, 4571, 4849, 1918, 1949, 2053, 6623, 6588, 5397, 526, 641, 4539, 74, 4944, 6063, 3862, 1166, 323, 3496, 4761, 5636, 7030, 762, 4885, 3691, 1136, 5020, 556, 1114, 3589, 3268, 651, 251, 5394, 6169, 501, 4221, 2144, 5798, 6380, 6814, 6222, 453, 4927, 3789, 3946, 3256, 6462, 897, 6170, 3229, 4667, 2770, 326, 1258, 6894, 838, 4881, 4688, 694, 4658, 3342, 593, 4604, 2825, 2503, 2420, 6122, 3091, 3411, 3080, 242, 398, 3562, 6276, 5907, 1326, 5757, 529, 3319, 4904, 4098, 3285, 3144, 1738, 886, 440, 1542, 4339, 3201, 2780, 4255, 3772, 57, 327, 2498, 3634, 6720, 1812, 3199, 190, 4824, 2851, 6371, 3468, 4362, 266, 5862, 5673, 649, 5769, 4938, 4717, 1591, 5130, 2026, 5721, 4607, 6010, 6307, 274, 1218, 100, 4726, 4921, 3278, 2671, 5047, 1317, 4574, 6687, 1429, 6672, 4750, 3806, 977, 3450, 6400, 6489, 2609, 5442, 6038, 2531, 5714, 895, 6457, 6808, 4263, 6350, 6681, 5710, 2286, 3037, 6281, 6142, 5884, 6673, 70, 5261, 1483, 6981, 833, 6509, 735, 544, 4573, 4353, 4420, 1579, 4758, 1621, 3878, 246, 6565, 4914, 2850, 3535, 4775, 497, 4839, 4327, 2143, 5979, 6937, 5415, 2029, 3471, 4480, 1212, 632, 136, 2820, 3024, 1283, 3058, 3341, 4106, 3729, 4570, 5881, 3314, 4597, 535, 4760, 698, 5995, 620, 1592, 4870, 6428, 6626, 3969, 3354, 3330, 5504, 2787, 3381, 5122, 6375, 5365, 2615, 5250, 1549, 6292, 4266, 6403, 3446, 3056, 4710, 5236, 3158, 4003, 4297, 5176, 320, 1221, 3181, 296, 2958, 5259, 5679, 3763, 105, 4111, 3556, 5038, 6031, 5341, 6250, 5200, 2030, 853, 4737, 6333, 5434, 1781, 3021, 1155, 41, 4184, 262, 3167, 5050, 6754, 82, 807, 882, 4058, 2062, 3401, 2521, 5502, 2076, 4243, 27, 179, 1898, 820, 3883, 2791, 1958, 1101, 232, 4819, 3294, 2682, 1242, 5918, 5193, 2871, 5457, 815, 4682, 2150, 1828, 6474, 1683, 5585, 490, 3204, 2873, 3157, 1010, 6334, 1282, 3519, 3441, 5395, 2399, 4446, 4289, 5192, 693, 4227, 6337, 2492, 3392, 782, 3438, 6321, 928, 5588, 6546, 3082, 5440, 1707, 3941, 2114, 2465, 5111, 1439, 4361, 3872, 6157, 6202, 1234, 2106, 3384, 4567, 797, 793, 1821, 4977, 6518, 2022, 213, 5671, 2066, 3458, 6644, 4588, 3987, 639, 3250, 569, 1497, 2565, 2933, 1777, 2633, 1640, 298, 4747, 3018, 2695, 6545, 2829, 6811, 4140, 1763, 6906, 352, 367, 1736, 1942, 2553, 2602, 5696, 2960, 859, 3910, 2297, 29, 4159, 97, 6627, 4716, 514, 5459, 5975, 4576, 3077, 6478, 2691, 2512, 2405, 5195, 4739, 6760, 1292, 3365, 4523, 4756, 4788, 2972, 6289, 1859, 5947, 2729, 1889, 5032, 1223, 3756, 543, 5616, 4765, 3902, 4169, 1313, 5233, 3731, 2486, 3318, 4345, 3163, 629, 1012, 6229, 3190, 2742, 2119, 249, 3767, 1255, 3610, 2823, 3638, 766, 2859, 1926, 6253, 227, 868, 6407, 305, 6640, 2591, 1139, 4164, 1459, 1399, 4427, 4794, 5600, 4357, 4185, 5773, 1565, 5281, 3512, 3541, 5578, 4879, 5851, 6755, 4101, 4751, 4564, 4213, 2992, 5309, 2333, 2237, 3574, 969, 4277, 4669, 996, 5599, 358, 2532, 5569, 6637, 1749, 6857, 4112, 3672, 2636, 6876, 5357, 1734, 6228, 3306, 6956, 5452, 3950, 2784, 4354, 6887, 1119, 3459, 5332, 4001, 267, 1206, 6649, 6542, 3728, 885, 3059, 5088, 4080, 5327, 5189, 5408, 5900, 5719, 6073, 5741, 5282, 3624, 1339, 1612, 6765, 5379, 1239, 841, 1569, 5409, 4018, 4611, 4419, 260, 4822, 5021, 1424, 6796, 5903, 3090, 4323, 1467, 5794, 4625, 800, 1848, 5807, 2036, 1251, 587, 3990, 5262, 40, 1807, 5703, 5351, 1269, 6583, 4832, 5330, 2351, 875, 4858, 6096, 1111, 408, 6393, 5746, 2090, 2642, 2741, 5145, 1912, 5735, 5988, 1276, 46, 6472, 1397, 4530, 4049, 6678, 5780, 5374, 6592, 2581, 7029, 4153, 6123, 4478, 6104, 6402, 2100, 946, 4286, 1298, 2218, 794, 2655, 5893, 1445, 1681, 434, 1257, 5678, 134, 5014, 5756, 6360, 1496, 5962, 6610, 2407, 2698, 2055, 5888, 2603, 1655, 3753, 4774, 2272, 3917, 695, 4013, 3726, 6249, 3222, 2202, 5004, 4772, 1587, 1022, 458, 307, 466, 508, 4489, 3121, 450, 5917, 640, 5400, 1808, 3209, 26, 279, 141, 4254, 3626, 3654, 657, 6632, 2976, 5252, 197, 5165, 2371, 5116, 3501, 1299, 1755, 2103, 3989, 3629, 2326, 5691, 3335, 2895, 6567, 2356, 1622, 827, 183, 761, 5933, 3863, 2386, 954, 6055, 1657, 5301, 5844, 5682, 5665, 268, 1814, 2483, 1570, 5211, 2699, 6014, 2320, 870, 6406, 594, 3905, 4779, 6690, 3378, 2368, 1088, 6959, 1906, 6447, 15, 6153, 144, 5268, 1737, 371, 2282, 1558, 2115, 2537, 4024, 5956, 5005, 6082, 2342, 1717, 670, 6881, 5977, 5447, 2765, 337, 5439, 662, 4787, 4436, 5868, 1919, 5180, 5013, 1669, 1228, 1826, 2560, 3472, 5953, 4981, 5396, 2254, 3436, 3374, 6551, 5432, 6264, 1765, 6616, 6501, 6325, 3696, 3678, 911, 1361, 4414, 4901, 470, 5346, 1541, 5518, 927, 1723, 4509, 2392, 6833, 3510, 6606, 1616, 2887, 2795, 3161, 610, 1782, 5391, 2402, 4228, 995, 4618, 6288, 3461, 3057, 4276, 2667, 1110, 333, 2723, 789, 3368, 1904, 4118, 3942, 2434, 681, 2920, 2630, 5082, 3598, 3295, 6132, 4259, 2059, 6164, 3349, 6538, 7021, 2558, 278, 2792, 2220, 1327, 3661, 2883, 215, 2542, 4338, 4035, 3824, 6763, 6041, 5531, 1751, 2806, 1818, 5423, 6147, 4115, 691, 3231, 5310, 844, 3038, 7018, 3973, 1264, 4174, 2406, 703, 6345, 4363, 2411, 4741, 1303, 2430, 612, 1710, 2848, 175, 1703, 1636, 2657, 3098, 3563, 1150, 3879, 1870, 563, 2111, 6013, 5323, 5704, 5425, 248, 2977, 18, 601, 907, 6744, 2984, 1975, 2762, 6840, 6901, 6167, 1381, 5660, 950, 6133, 6499, 549, 5652, 4161, 6340, 3388, 4141, 2923, 4736, 6895, 1775, 3266, 17, 2919, 4594, 1998, 1036, 1208, 3054, 1144, 5699, 1190, 2688, 6846, 4239, 6519, 24, 3395, 2686, 1741, 4796, 1039, 4258, 3714, 5901, 3101, 1829, 6522, 3719, 4752, 4781, 4332, 5161, 388, 1915, 4343, 5619, 6046, 638, 4417, 3523, 1156, 2854, 3595, 2357, 4173, 366, 4127, 5398, 675, 5302, 753, 2777, 4429, 813, 5712, 1092, 3847, 3112, 5562, 4041, 6216, 2632, 4273, 5501, 277, 2052, 5388, 653, 4602, 3919, 4162, 3443, 1267, 2721, 6356, 1238, 3773, 2322, 6593, 3579, 2359, 862, 5896, 6630, 1595, 4046, 665, 6258, 2697, 2580, 5734, 6110, 5961, 1940, 4936, 4232, 3511, 6494, 5371, 3641, 2414, 5840, 1530, 1551, 2375, 2104, 3067, 4075, 1465, 1637, 6, 313, 6804, 1325, 198, 5172, 1488, 5895, 3967, 5168, 3064, 3066, 2079, 6217, 3565, 6572, 3788, 3043, 1179, 586, 212, 4466, 5178, 5963, 6324, 3547, 252, 2493, 4942, 363, 2669, 5960, 4023, 4198, 2361, 1148, 3993, 4531, 1605, 4930, 6645, 6479, 1934, 5873, 2708, 4786, 4644, 1979, 5372, 1434, 505, 6889, 2555, 3930, 5134, 116, 5163, 2339, 2313, 1133, 4216, 4722, 1943, 957, 1937, 4664, 4662, 6426, 4038, 3403, 1272, 1576, 4182, 4034, 92, 4513, 36, 5191, 3379, 4199, 6394, 715, 5879, 5904, 3022, 3017, 5338, 6745, 1288, 2959, 2264, 5863, 2946, 1216, 1575, 5380, 748, 1426, 1977, 2165, 4002, 430, 4483, 6966, 5528, 185, 5574, 6713, 1929, 4652, 5911, 4888, 948, 2418, 247, 2291, 941, 4941, 6144, 5299, 2583, 1203, 324, 2956, 2707, 3246, 6421, 3292, 6480, 5753, 3028, 3322, 6520, 4762, 210, 5496, 3376, 742, 6039, 76, 5036, 4693, 988, 485, 4962, 4732, 2911, 5238, 3724, 2517, 2674, 1492, 4697, 1815, 257, 2154, 3013, 1342, 3130, 5228, 1065, 4861, 5003, 2013, 1519, 1951, 5059, 4615, 5048, 2355, 2457, 1618, 1406, 3477, 3804, 5392, 6113, 3982, 5813, 634, 2703, 4488, 285, 5159, 507, 602, 4649, 5659, 2176, 4172, 5080, 5190, 1270, 2899, 3457, 4474, 545, 4215, 2181, 2397, 5786, 1048, 1309, 3840, 5825, 650, 418, 3886, 211, 2638, 4006, 3003, 5352, 4912, 6023, 3576, 4969, 4386, 3439, 5177, 4729, 1172, 2470, 4515, 5487, 444, 6725, 6493, 3405, 865, 5265, 5553, 2201, 6527, 697, 3560, 1137, 890, 1712, 2921, 2785, 4891, 176, 647, 6674, 4657, 3532, 6280, 2214, 2547, 184, 1040, 5289, 439, 6021, 580, 1732, 474, 106, 3713, 1626, 787, 3605, 5623, 5218, 6508, 538, 1773, 1752, 2617, 6617, 2489, 1183, 2948, 1446, 3137, 4219, 2912, 1295, 1891, 4837, 5728, 696, 6917, 5992, 723, 1897, 3081, 3264, 2750, 680, 5847, 5726, 1202, 2156, 4568, 2158, 4698, 4900, 4976, 3396, 306, 3559, 5041, 714, 2452, 3769, 2185, 1001, 7017, 2244, 3334, 1585, 478, 1568, 5985, 2077, 38, 4937, 4676, 3888, 3505, 4964, 791, 1552, 34, 3504, 5492, 2601, 4078, 565, 405, 5912, 728, 491, 145, 2524, 2589, 1511, 2015, 5133, 191, 2543, 2733, 4413, 1856, 1067, 1596, 2080, 5506, 463, 2300, 2546, 6239, 1431, 4929, 2772, 6344, 966, 1187, 6193, 5803, 3099, 2626, 1556, 4749, 4125, 5892, 1149, 1027, 6631, 4887, 3068, 6870, 606, 1308, 5867, 2033, 289, 2318, 6530, 95, 465, 2400, 4214, 2986, 5783, 239, 2354, 5401, 5334, 52, 2552, 1836, 5451, 3409, 6566, 448, 4495, 2014, 6465, 3777, 3513, 4650, 5723, 2796, 1670, 4554, 6865, 6443, 6449, 5470, 3855, 1721, 3829, 6162, 3803, 2312, 2, 3051, 6641, 1153, 256, 158, 6067, 2747, 915, 1947, 4042, 96, 5115, 6515, 2804, 3304, 3744, 6286, 6496, 3890, 6466, 3239, 2045, 5634, 686, 3502, 3111, 3170, 5091, 4763, 3553, 5384, 5229, 2472, 3802, 1970, 479, 2843, 208, 1351, 3566, 6323, 1301, 3076, 6413, 6042, 3924, 3200, 3702, 4315, 1252, 1347, 4866, 4975, 876, 678, 843, 2239, 21, 3086, 1580, 3960, 4238, 5545, 6372, 6769, 6564, 6159, 1469, 5935, 1354, 6965, 1933, 2388, 6145, 5820, 476, 4792, 712, 6893, 6683, 3444, 4884, 6107, 3281, 5999, 5002, 1779, 873, 5010, 6624, 5610, 5702, 1844, 7022, 1428, 887, 2566, 699, 3286, 1837, 5815, 1046, 2140, 3178, 6389, 2937, 2607, 48, 5565, 2490, 2160, 4769, 336, 6352, 4826, 1914, 1987, 301, 5916, 5940, 3980, 3873, 1487, 3834, 259, 379, 4310, 3449, 7008, 2571, 6513, 4842, 6928, 6523, 6657, 6442, 6983, 2592, 6099, 3835, 3487, 5463, 3926, 3329, 4893, 4472, 3210, 108, 3907, 1391, 3951, 5716, 2377, 6260, 3475, 2225, 5521, 3843, 6454, 6211, 2548, 3957, 3275, 3039, 1932, 1209, 1888, 3491, 5269, 574, 6062, 4260, 6662, 3196, 6537, 1181, 3463, 2037, 5283, 831, 1988, 4103, 3580, 4883, 6261, 6809, 3554, 5664, 512, 1196, 2109, 2130, 5720, 2044, 5608, 4867, 1886, 4057, 2051, 5626, 584, 1916, 2693, 4699, 3677, 360, 2556, 930, 2335, 387, 814, 181, 6829, 6077, 6693, 5627, 3911, 3027, 3543, 3864, 2763, 6151, 1140, 6017, 3657, 4264, 1366, 5105, 3288, 3981, 5557, 3844, 2401, 410, 3223, 5898, 4218, 1619, 515, 2952, 6065, 3252, 2330, 6604, 6072, 63, 2766, 1864, 4790, 6128, 786, 1769, 5473, 3656, 2020, 3816, 435, 3551, 645, 6573, 451, 3172, 1015, 4376, 237, 1343, 1835, 3474, 3913, 5058, 2284, 5500, 5009, 5209, 3625, 5952, 6579, 2078, 413, 2718, 5164, 5477, 931, 500, 6684, 494, 3123, 2240, 4759, 6934, 5796, 4955, 1584, 4768, 6076, 3138, 1068, 1214, 6279, 4703, 3937, 6184, 5897, 1073, 56, 467, 6296, 4055, 5364, 174, 2736, 2738, 5441, 608, 592, 1330, 1687, 3273, 2515, 182, 7001, 481, 1315, 2595, 3309, 2934, 4389, 6734, 3651, 3813, 6601, 2496, 5293, 3805, 5594, 1510, 5558, 804, 6040, 4307, 5360, 4498, 6415, 725, 1611, 867, 917, 1498, 362, 4581, 4440, 516, 4890, 4678, 3127, 6341, 2831, 4166, 386, 7014, 6339, 6963, 188, 7016, 692, 4802, 6642, 6156, 3485, 945, 5642, 5318, 6347, 3793, 1753, 6213, 1754, 1534, 2485, 5316, 2872, 5210, 5672, 5618, 1485, 1799, 7010, 555, 1, 5326, 5499, 4707, 4242, 5845, 4980, 6306, 4069, 4720, 6907, 6709, 6191, 1146, 3311, 3184, 4627, 4668, 5886, 6100, 6120, 4135, 6140, 2344, 3715, 4437, 5039, 3737, 5592, 3853, 4431, 222, 912, 4300, 131, 5624, 1019, 3759, 5068, 2175, 6265, 734, 5924, 5540, 201, 5650, 1625, 1699, 796, 4128, 4687, 4360, 165, 7028, 6711, 146, 6171, 1971, 2126, 2637, 6988, 2717, 5595, 4619, 2927, 1608, 6137, 3010, 4677, 3462, 5435, 6612, 5493, 163, 5454, 6973, 3262, 4551, 6255, 4847, 2442, 1594, 5204, 2559, 1567, 6050, 4093, 2427, 1233, 5437, 6070, 660, 1833, 2166, 4917, 4047, 6694, 3526, 4956, 4626, 1930, 6768};
        int n = 7194, maxSum = 9254;
        assertEquals(94, new Solution2().maxCount(banned, n, maxSum));
    }

    @Test
    void test4() {
        int[] banned = {12};
        int n = 610;
        int maxSum = 2199;
        assertEquals(65, new Solution2().maxCount(banned, n, maxSum));
    }
}